Betweenness is a well-known centrality measure that ranks the nodes accordingto their participation in the shortest paths of a network. In severalscenarios, having a high betweenness can have a positive impact on the nodeitself. Hence, in this paper we consider the problem of determining how much avertex can increase its centrality by creating a limited amount of new edgesincident to it. In particular, we study the problem of maximizing thebetweenness score of a given node -- Maximum Betweenness Improvement (MBI) --and that of maximizing the ranking of a given node -- Maximum RankingImprovement (MRI). We show that MBI cannot be approximated in polynomial-timewithin a factor $(1-\frac{1}{2e})$ and that MRI does not admit anypolynomial-time constant factor approximation algorithm, both unless $P=NP$. Wethen propose a simple greedy approximation algorithm for MBI with an almosttight approximation ratio and we test its performance on several real-worldnetworks. We experimentally show that our algorithm highly increases both thebetweenness score and the ranking of a given node ant that it outperformsseveral competitive baselines. To speed up the computation of our greedyalgorithm, we also propose a new dynamic algorithm for updating the betweennessof one node after an edge insertion, which might be of independent interest.Using the dynamic algorithm, we are now able to compute an approximation of MBIon networks with up to $10^5$ edges in most cases in a matter of seconds or afew minutes.
展开▼
